package leetcode;

import list.LinkedListCreate;
import list.ListNode;

public class ReverseNodesInKGroup {

	public static void main(String[] args) {
		ReverseNodesInKGroup object = new ReverseNodesInKGroup();
		int[] nums = {9, 8, 5, 6, 10, 1, 3, 7};
		ListNode head = LinkedListCreate.createList(nums);
		LinkedListCreate.printList(head);
		head = object.reverseKGroup(head, 2);
		LinkedListCreate.printList(head);
	}
	
	public ListNode reverseKGroup(ListNode head, int k) {
        if(head == null || head.next == null){
        	return head;
        }
        ListNode[] res = reverseListNode(head, k);
        ListNode[] temp = new ListNode[2];
        System.out.println("res[0]: " + res[0].val + "res[1]:" + res[1].val);
        ListNode newHead = res[0];
        while(res[1] != null){
        	temp = reverseListNode(res[1].next, k);
        	res[1].next = temp[0];
        	res = temp;
        }
        return newHead;
    }
	
	//返回反转之后的头结点的尾结点，ListNode[0]为头结点，ListNode[1]为尾结点
	public ListNode[] reverseListNode(ListNode head, int k){
		if(head == null){
			return new ListNode[]{head, null};
		}else{
			System.out.println("head: " + head.val);
		}
		//首先判断以head开头的长度是否大于等于k
		int length = 1;
		ListNode node = head;
		ListNode tail = head;
		while(node.next != null && length < k){
			node = node.next;
			tail = node;
			length++;
		}
		if(length < k){
			return new ListNode[]{head, null};
		}
		ListNode linkNode = tail.next;
		
//		System.out.println("tail: " + tail.val + "linkNode:" + linkNode.val);
		node = head;
		ListNode pre = null;
		ListNode next = null;
		while(node != null && length > 0){
			next = node.next;
			node.next = pre;
			pre = node;
			node = next;
			length--;
		}
		//此时的head肯定为反转之后的尾结点
		head.next = linkNode;
		return new ListNode[]{pre, head};
	}
}
